class Solution
{
public:
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
    {
        stack<int> s;
        unordered_map<int, int> nextGreaterMap;
        for (auto it = nums2.rbegin(); it != nums2.rend(); ++it)
        {
            while (!s.empty())
            {
                if (s.top() > *it)
                {
                    nextGreaterMap.insert({*it, s.top()});
                    break;
                }
                else
                {
                    s.pop();
                }
            }
            if (s.empty())
            {
                nextGreaterMap.insert({*it, -1});
            }
            s.push(*it);
        }
        for (auto &num : nums1)
        {
            num = nextGreaterMap[num];
        }
        return nums1;
    }
};